Beam Search

在之前的貼文有提到機械翻譯的 Seq2Seq 架構中，分為 training 和 inference 兩個步驟。在訓練過程中，模型會經由訓練學習以來源語言為主的 encoder 和目標語言為主的 decoder 語言模型的參數。而在推測步驟中，則是計算給定輸入序列 x， 生成序列，y 的條件機率（conditional probability），或以 p(y|x) 表示。

給定一來源語言輸入，需要從已訓練完成的模型中，由 decoder 產生最有可能的目標語言翻譯。decoder 的功能近似於語言生成的部分，但相較於 decoder 生成序列的第一個輸出字詞，需要由 encoder 來生成，機械翻譯是根據 encoder 的輸入序列所算出的聯合機率（joint probability），找出擁有最大 p(y|x) 的最佳序列，在此被稱為 y*。

在語言生成模型中，我們也提到一個 greedy 方法，來做序列生成。在機械翻譯的 inference 步驟，同樣也可以應用 greedy 的搜尋方式，在每一 decoder 狀態位置，給定來源輸入序列和在此位置前的生成序列估算出的 joint probability，生成會導致到此位置的最大條件機率。這個做法在傳統訓練統計語言模型 Hidden Markov Model 被稱為 Viterbi decoder。

Viterbi decoder 之所以 greedy ，是因為這個 decoder 總是看局部（到該位置的最大條件機率值），然而在某些應用上，如機械翻譯，我們希望能有多個輸出，又或擔心 Viterbi decoder 因為其 greedy 的方式，而遺漏掉更佳的序列。在這樣的情況下，就需要用一種稱為 Beam Search 的方法來做 decode。

最簡單的 Beam Search 演算法，是在每一時步中保持一定數量的輸出語詞作為候選名單，而在輸出最終結果時將列在候選名單上的序列輸出。由於在選入單詞於候選名單中，必定依據該時步的機率分佈大小排序，由最大機率詞語往下選多個候選詞語，能保證在候選名單中的輸出句子，必定都有較高的機率估算。其次，因為有多個候選名單並列，所以可以免除單一輸出遺漏掉最佳輸出的可能。

這個候選名單的大小，透過設定 Beam Width 的參數來決定。而 Viterbi decoder 可以視為 Beam Search 演算法，將 Beam Width 參數設為 1 的特例。

最簡單的 Beam Search 演算法的步驟可以簡述如下，若 Beam Width = B：

1. 建立一個搜尋樹，該樹的根節點為開始符號（非序列的第一個單詞）。
2. 由序列的左到右開始，順序生成目標語言序列，同時成長對應的搜尋樹。
3. 在生成序列的每一步，對搜尋樹的每個葉節點，選取 B 個擁有最高條件機率的生成單詞，並生成 B 個子節點。
4. 在成長搜尋樹後，進行剪枝的工作，只留下 B 個最高條件機率的葉節點後，再進行下一個位置的序列生成。

剪枝的目的在於，Beam Search 在每一步都對前一位置生成每一個序列，繼續產生 B 個候選名單，如此一來造成搜尋空間的指數爆炸問題。透過剪枝的方法，在每一步都只選取較高機率的 B 個候選序列生成，而保持搜尋效率，在某種程度也能維持生成序列的品質。

Beam search 異於其他的 search 演算法，如 Breadth / Depth first search 演算法，在於該演算法能拜訪搜尋樹中所有的節點，並找出 exact 的解。然而，Beam search 透過剪枝的方式，只能搜尋部分節點，所以是 approximate search 演算法。

我們將在最後一個小節提到該如何對RNN 和 Beam search 演算法的類神經機械翻譯系統做除錯分析（Error analysis）。

另外，雖然 Beam search 的演算法看似簡單，但在使用時卻有許多細節需要注意，以下把課程中提到的要點摘錄如下：

1. 消除長度對計算機率影響（Length Normalization）
2. 如何選擇 Beam Width 參數（The Choice of Beam Width）

消除長度對計算機率影響（Length Normalization）：

然而在生成序列時必須要對預估序列的似然機率（likelihood probability）並在給定來源序列找出最大可能的條件機率值。最大可能的似然機率值的估算是每一位置的狀態和輸出機率乘積，而此機率乘積顯然地會隨著產生序列的長度而衰減，於是 decoder 產生的序列會偏好較短的序列。因為比起較長的序列，較短序列的似然機率會因為長度偏差而大得多。

另外一個問題，則是因為似然機率是許多機率的乘積，鑑於機率的值域在 [0, 1] 的區間，於是通常會造成超出中央處理單元的浮點數計算精度可以容納的程度。

因為在機械翻譯中 decoder 的輸出序列長度是不定的，所以輸出序列長度本身也是一個變數，需要考慮在內。為了解決上述因為長度所造成的似然機率估算偏差，通常在計算似然機率時，會使用以下的方法來克服：

1. 關於超過浮點數計算精度的部分：與其直接使用機率值乘積，最佳的方式則是利用 log 函式轉換使之能夠處理更多乘積項。
2. 長度偏差的影響：即使是利用 log 函式轉換使乘積變為總和，仍無法避免長度偏差。在此，我們可對似然機率估算結果做長度校正的程度。這個長度校正的方法只是對似然機率估算總和取平均，也是除以產生序列長度的部分。

長度校正的部分，可利用一參數 - 來控制長度校正的強度。因為序列長度的分佈通常為 exponential decay，也就是長度較長的序列通常較為稀少，透過選取小於 1 的 值來使較長的序列在做長度校正會有比 值等於 1 的值（完全取平均）有較大的機率值，也容易被選出。但 的值據經驗通常選在 0.7。

另外，在實際使用 Beam Search 來產生 decoder 序列時，通常會嘗試不同的序列長度，如上圖投影片所示，由列舉序列長度為 1...30，並依次計算最大似然機率，以求得最佳的生成目標序列長度。

如何選擇 Beam Width 參數（The choice of Beam Width）

Beam Width 的參數大小，會造成演算法效率的不同。若 Beam Width 選取的過大，則計算效能較差，但比較容易囊括真正最好的輸出序列（由於 Viterbi decoder 是 greedy 的解法，並不能保證得到全域最佳解）。而 Beam Width 選取過小，則計算效能較高，執行速度較快，但必較容易遺漏真正最好的輸出序列。

其他的在調整 Beam Width 參數，可以如其他機械學習模型調整參數的方式，利用 grid search，對一個範圍的 Beam Width 可能值做逐一測試。要注意的是，當生成 Beam Width 參數範圍時，不要以均等的步距來產生。因為，當 Beam Width 的值愈大時，增加 Beam Width 可以產生的效能增益會減小。

Error analysis

除錯分析的整體概念包含以下兩個步驟：

1. 將系統拆成較小的單元。
2. 選定一個量測的方法，該量測方法可以判定哪一個單元出錯。

以對前述的類神經機械翻譯系統為例，我們可以將此系統分為兩個部分，一個是負責估算參數及計算分佈機率的 RNN 模型，另一個則是由 Beam search 負責在已估算好的似然機率中找出最有可能的候選序列們。

而在偵錯的時候，主要把握一個大原則：準備一組人類翻譯內容為應當的最佳目標語言產生序列，此序列所由 RNN 計算出來的估算機率則最佳機率值（在眾多可能產生序列中理應擁有最大機率），用 y* 表示。並以以下原則來判別是哪一個階段出錯（RNN 參數估算有錯？還是 Beam search 的參數沒有設對）

• 倘若 p(y*|x) 經過 RNN 估算後非最大值，那麼就是負責估算機率的 RNN 有錯誤。
• 倘若 p(y*|x) 經過 RNN 估算後為最大值，但不出現在 Beam search 的候選名單中，那麼就是 Beam search 的步驟出錯。

最後將所有的實例以此原則分析，並挑出實例中哪一個單元（RNN 或是 Beam search？）出錯的比例較高，便從修復該單元開始。

以上原則可以對照課程投影片來看。